package sliding_window

import "strings"

//395. 给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串，要求该子串中的【每一字符】出现次数都不少于 k 。返回这一子串的长度。

//示例 1：
//输入：s = "aaabb", k = 3
//输出：3
//解释：最长子串为 "aaa" ，其中 'a' 重复了 3 次。
//示例 2：
//
//输入：s = "ababbc", k = 2
//输出：5
//解释：最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。

//滑动窗口
//我们枚举最长子串中的【字符种类数目】，它最小为 1，最大为 ∣Σ∣（字符集的大小，本题中为 26）。
//对于给定的字符种类数量 t，我们维护滑动窗口的左右边界 l,r、滑动窗口内部每个字符出现的次数 cnt，以及滑动窗口内的字符种类数目 total。
//当 total>t 时，我们不断地右移左边界 l，并对应地更新 cnt 以及 total，直到 total≤t 为止。这样，对于任何一个右边界 r，我们都能找到最小的 l（记为 lmin ），使得 s[lmin...r] 之间的字符种类数目不多于 t。
//对于任何一组 l_{min}, ,r 而言，如果 s[lmin...r] 之间存在某个出现次数小于 k （且不为 0，下文不再特殊说明）的字符，我们可以断定：对于任何 l′ ∈(l min,r) 而言，s[l′ ...r] 依然不可能是满足题意的子串，因为：
//要么该字符的出现次数降为 0，此时子串内虽然少了一个出现次数小于 k 的字符，但字符种类数目也随之小于 t 了；
//要么该字符的出现次数降为非 0 整数，此时该字符的出现次数依然小于 k。
//根据上面的结论，我们发现：当限定字符种类数目为 t 时，满足题意的最长子串，就一定出自某个s[lmin ...r]。因此，在滑动窗口的维护过程中，就可以直接得到最长子串的大小。
//此外还剩下一个细节：如何判断某个子串内的字符是否都出现了至少 k 次？我们当然可以每次遍历 cnt 数组，但是这会带来 O(∣Σ∣) 的额外开销。
//我们可以维护一个计数器 less，代表当前出现次数小于 k 的字符的数量。注意到：每次移动滑动窗口的边界时，只会让某个字符的出现次数加一或者减一。对于移动右边界 l 的情况而言：
//当某个字符的出现次数从 0 增加到 1 时，将 less 加一；
//当某个字符的出现次数从 k−1 增加到 k 时，将 less 减一。
//对于移动左边界的情形，讨论是类似的。
//通过维护额外的计数器 less，我们无需遍历 cnt 数组，就能知道每个字符是否都出现了至少 k 次，同时可以在每次循环时，在常数时间内更新计数器的取值。读者可以自行思考 k=1 时的处理逻辑
//时间复杂度：O(N⋅∣Σ∣+∣Σ∣^2 )，其中 N 为字符串的长度，Σ 为字符集，本题中字符串仅包含小写字母，因此 ∣Σ∣=26。我们需要遍历所有可能的 t，共 ∣Σ∣ 种可能性；
//内层循环中滑动窗口的复杂度为 O(N)，且初始时需要 O(∣Σ∣) 的时间初始化 cnt 数组。
//空间复杂度：O(∣Σ∣)

func longestSubstring(s string, k int) (ans int) {
	//默认26个字符集，也就是26个字符种类
	for t := 1; t <= 26; t++ {
		cnt := [26]int{} //记录每个字符出现次数
		//左指针，滑动窗口内字符种类数量，出现次数小于k的字符的数量
		l, total, lessK := 0, 0, 0
		//expands 窗口
		for r, ch := range s {
			ch -= 'a'
			if cnt[ch] == 0 { //新字符
				total++ //滑动窗口内字符种类数量
				lessK++ //出现次数小于 k 的字符的数量
			}
			cnt[ch]++         //字符出现次数加1
			if cnt[ch] == k { //expands 窗口的时候，如果等于K，则减少lessK的值
				lessK--
			}

			//shrinks 窗口
			//窗口内的字符种类数量大于给定的字符种类数量
			for total > t {
				ch := s[l] - 'a' //移出数据
				if cnt[ch] == k {
					lessK++
				}
				cnt[ch]--

				//对称操作，完全移除后，更新窗口内字符种类数量和出现次数小于K的字符的数量
				if cnt[ch] == 0 {
					total--
					lessK--
				}

				l++
			}

			//没有出现次数小于K的字符，结果集都是>=k的数据
			if lessK == 0 {
				ans = max(ans, r-l+1)
			}
		}
	}
	return ans
}

//对于字符串s,如果存在某个字符ch,它的出现次数大于0且小于k,则任何包含ch的【子串】都不可能满足要求。
//也就是说，我们将字符串按照ch切分成若干段,则满足要求的最长子串一定出现在某个被切分的段内，而不能跨越
//一个或多个段，因此可以考虑用分治法解决
func longestSubstringDC(s string, k int) (ans int) {
	if s == "" {
		return
	}

	cnt := [26]int{}
	for _, ch := range s {
		cnt[ch-'a']++ // 0:3,1:2,2:0,.....,25:0
	}

	var split byte
	for i, c := range cnt[:] {
		if 0 < c && c < k {
			split = 'a' + byte(i) //98
			break
		}
	}

	if split == 0 {
		return len(s)
	}

	for _, subStr := range strings.Split(s, string(split)) {
		ans = max(ans, longestSubstringDC(subStr, k))
	}
	return
}
